LeetCode 83、删除排序链表中的重复元素

一、题目描述

给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。

二、题目解析

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        // 从链表的头节点开始访问每一个节点
        ListNode cur = head;

        // 在访问过程中，只要当前节点和当前节点的下一个节点有值，就不断访问下去
        while(cur != null && cur.next != null) {

            // 当前节点和当前节点的下一个节点有两种关系

            // 1、当前节点和当前节点的下一个节点相同，此时要删除重复元素
            // 由于链表已经是排序的，所以去重操作只需要跳过后面这个重复的节点就行
            if(cur.val == cur.next.val) {

                // 执行这个操作之后，cur.next 被跳过去了
                cur.next = cur.next.next;

            // 2、当前节点和当前节点的下一个节点不相同，那么 cur 这个节点可以保留下来，继续访问后面的节点
            } else {
                // 继续访问后面的节点
                cur = cur.next;
            }
        }

        // 返回链表的头节点就是结果
        return head;
    }
}

**2、**C++代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        // 从链表的头节点开始访问每一个节点
        ListNode *cur = head;

        // 在访问过程中，只要当前节点和当前节点的下一个节点有值，就不断访问下去
        while(cur != NULL && cur->next != NULL) {

            // 当前节点和当前节点的下一个节点有两种关系

            // 1、当前节点和当前节点的下一个节点相同，此时要删除重复元素
            // 由于链表已经是排序的，所以去重操作只需要跳过后面这个重复的节点就行
            if(cur->val == cur->next->val) {

                // 执行这个操作之后，cur->next 被跳过去了
                cur->next = cur->next->next;

            // 2、当前节点和当前节点的下一个节点不相同，那么 cur 这个节点可以保留下来，继续访问后面的节点
            } else {
                // 继续访问后面的节点
                cur = cur->next;
            }
        }

        // 返回链表的头节点就是结果
        return head;
    }
};

3、Python 代码

# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/
class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        # 从链表的头节点开始访问每一个节点
        cur = head

        # 在访问过程中，只要当前节点和当前节点的下一个节点有值，就不断访问下去
        while cur and cur.next :

            # 当前节点和当前节点的下一个节点有两种关系

            # 1、当前节点和当前节点的下一个节点相同，此时要删除重复元素
            # 由于链表已经是排序的，所以去重操作只需要跳过后面这个重复的节点就行
            if cur.val == cur.next.val :

                # 执行这个操作之后，cur.next 被跳过去了
                cur.next = cur.next.next

            # 2、当前节点和当前节点的下一个节点不相同，那么 cur 这个节点可以保留下来，继续访问后面的节点
            else:
                # 继续访问后面的节点
                cur = cur.next

        # 返回链表的头节点就是结果
        return head

四、复杂度分析

• 时间复杂度：O(n)，其中 n 是链表的长度。
• 空间复杂度：O(1)。